iT邦幫忙

2021 iThome 鐵人賽

DAY 23
0

介紹:

k-平均演算法(英文:k-means clustering,以下簡稱為 k-means )是一種非監督式的學習方法,其主要的目標是對未標記的資料進行分群。什麼意思呢?

k-means 的判斷邏輯其實跟 KNN 一樣,都是物以類聚。我們在介紹 KNN 的時候曾經舉例:假設你的鄰居都是有錢人,那麼你有十之八九也是有錢人。
那麼 k-means 在做的事情就是:我們不知道誰是有錢人,但是有錢人肯定會聚在一起,窮人也是。

但是資料並不會自己長腳然後湊成一堆,這個時候我們該怎麼將他們分群呢?
答案是找出群集中心。這就像是一群人剛剛湊在一起大家都不熟,但過了一陣子之後便會有一些小團體出現,而在每個團體中總會有人成為領頭羊,而這幾隻領頭羊就是我們要找的群集中心了。
(當然,隨著時間推進,各個團體內的領頭羊也可能會換人,直到最適合的領導者出現為止。)

步驟如下:

  1. 首先決定要分成 k 組,然後在特徵空間中隨機選 k 個點當作群集中心。
    (資料的維度是幾維,特徵空間就有幾維)
  2. 將每一筆資料分別對每一個群集中心計算距離。
  3. 將每一筆資料分類到離自己最近的群集中心。
  4. 每個群內都獲得了新的資料,用這些資料更新各組的群集中心。
  5. 直到每一組的群集中心不再有變動為止。

數學式:

  1. 我們將資料分為 k 群,自然就會有 k 個群集中心。而我們會希望每一群的資料都能跟群集中心距離愈短愈好,因此:

    已知觀測集https://chart.googleapis.com/chart?cht=tx&chl=%24%7B%5Cdisplaystyle%20(x_%7B1%7D%2Cx_%7B2%7D%2C...%2Cx_%7Bn%7D)%7D%24,其中每個觀測都是一個 d 維的實向量,而我們在做的就是要想辦法求出各個群組內部最小的均方誤差總和。
    https://chart.googleapis.com/chart?cht=tx&chl=%24%7B%5Cdisplaystyle%20%7B%5Cunderset%20%7B%5Cmathbf%20%7BS%7D%20%7D%7B%5Coperatorname%20%7Barg%5C%2Cmin%7D%20%7D%7D%5Csum%20_%7Bi%3D1%7D%5E%7Bk%7D%5Csum%20_%7B%5Cmathbf%20%7Bx%7D%20%5Cin%20S_%7Bi%7D%7D%5Cleft%5C%7C%5Cmathbf%20%7Bx%7D%20-%7B%5Cmu%20%7D_%7Bi%7D%5Cright%5C%7C%5E%7B2%7D%7D%24

    https://chart.googleapis.com/chart?cht=tx&chl=%20%24%7B%5Cmu%20%7D_%7Bi%7D%24 代表群集中心,‖https://chart.googleapis.com/chart?cht=tx&chl=%24%7Bx%7D-%7B%5Cmu%20%7D_%7Bi%7D%24‖就是算歐式距離,而S為分割的群組集合。

  2. 計算每個群集內的資料,其中每個https://chart.googleapis.com/chart?cht=tx&chl=%24%7B%5Cdisplaystyle%20x_%7Bp%7D%7D%24都只被分配到一個確定的聚類https://chart.googleapis.com/chart?cht=tx&chl=%24%7B%5Cdisplaystyle%20S%5E%7Bt%7D%7D%24
    https://chart.googleapis.com/chart?cht=tx&chl=%24%7B%5Cdisplaystyle%20S_%7Bi%7D%5E%7B(t)%7D%3D%5Cleft%5C%7Bx_%7Bp%7D%3A%5Cleft%5C%7Cx_%7Bp%7D-m_%7Bi%7D%5E%7B(t)%7D%5Cright%5C%7C%5E%7B2%7D%5Cleq%20%5Cleft%5C%7Cx_%7Bp%7D-m_%7Bj%7D%5E%7B(t)%7D%5Cright%5C%7C%5E%7B2%7D%5Cforall%20j%2C1%5Cleq%20j%5Cleq%20k%5Cright%5C%7D%7D%24

  3. 更新群集中心。
    https://chart.googleapis.com/chart?cht=tx&chl=%24%7B%5Cdisplaystyle%20m_%7Bi%7D%5E%7B(t%2B1)%7D%3D%7B%5Cfrac%20%7B1%7D%7B%5Cleft%7CS_%7Bi%7D%5E%7B(t)%7D%5Cright%7C%7D%7D%5Csum%20_%7Bx_%7Bj%7D%5Cin%20S_%7Bi%7D%5E%7B(t)%7D%7Dx_%7Bj%7D%7D%24

實作

我們隨機生成 200 個點,然後用 k-means 將他們分成 5 群:

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans

x = np.random.rand(200,2)  # 將200個值隨機分佈在2維上
clf = KMeans(n_clusters=5)  # 分成5類
clf.fit(x)

# 將點逐一染色
for i in range(0,100):
    if clf.labels_[i] == 0:
        plt.scatter(x[i][0], x[i][1], color='red')
    elif clf.labels_[i] == 1:
        plt.scatter(x[i][0], x[i][1], color='blue')
    elif clf.labels_[i] == 2:
        plt.scatter(x[i][0], x[i][1], color='green')
    elif clf.labels_[i] == 3:
        plt.scatter(x[i][0], x[i][1], color='pink')
    elif clf.labels_[i] == 4:
        plt.scatter(x[i][0], x[i][1], color='orange')

plt.autoscale()
plt.grid()  # grid()用來顯示網格
plt.show()

reference

https://chih-sheng-huang821.medium.com/%E6%A9%9F%E5%99%A8%E5%AD%B8%E7%BF%92-%E9%9B%86%E7%BE%A4%E5%88%86%E6%9E%90-k-means-clustering-e608a7fe1b43
https://zh.wikipedia.org/wiki/K-%E5%B9%B3%E5%9D%87%E7%AE%97%E6%B3%95

其實機器學習還有很多可以講的內容,但是礙於篇幅的關係,機器學習的部份將先告一段落。明天將開始進入深度學習的環節!


上一篇
Day 22 貝式分類器 Bayesian Classifier
下一篇
Day 24 深度學習與人工神經網路
系列文
新手也想開始認識機器學習30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

我要留言

立即登入留言